#include <stdio.h>
#include <math.h>

typedef struct {
    double x, y;
} Point;

Point line_intersection(Point line1_start, Point line1_end, Point line2_start, Point line2_end) {
    Point intersection;
    double A1, B1, C1, A2, B2, C2, det;

    A1 = line1_end.y - line1_start.y;
    B1 = line1_start.x - line1_end.x;
    C1 = line1_start.x * line1_end.y - line1_end.x * line1_start.y;

    A2 = line2_end.y - line2_start.y;
    B2 = line2_start.x - line2_end.x;
    C2 = line2_start.x * line2_end.y - line2_end.x * line2_start.y;

    det = A1 * B2 - A2 * B1;

    if (fabs(det) < 1e-6) {
        // 平行线
        intersection.x = intersection.y = 0.0;
    } else {
        intersection.x = (B2 * C1 - B1 * C2) / det;
        intersection.y = (A1 * C2 - A2 * C1) / det;
    }

    return intersection;
}

void calculate_all_tangent_lines(Point centers[], double radius, Point* intersection_points, int* num_intersections) {
    *num_intersections = 0;

    for (int i = 1; i < *num_intersections - 1; i++) {
        double x1 = centers[i - 1].x;
        double y1 = centers[i - 1].y;
        double x2 = centers[i].x;
        double y2 = centers[i].y;
        double x3 = centers[i + 1].x;
        double y3 = centers[i + 1].y;

        double angle1 = atan2(y2 - y1, x2 - x1);
        double angle2 = atan2(y3 - y2, x3 - x2);

        double slope1 = angle1;
        double slope2 = angle2;

        double x_t1_up = x1 + radius * sin(slope1);
        double y_t1_up = y1 - radius * cos(slope1);
        double x_t2_up = x2 + radius * sin(slope1);
        double y_t2_up = y2 - radius * cos(slope1);

        double x_t1_down = x1 - radius * sin(slope1);
        double y_t1_down = y1 + radius * cos(slope1);
        double x_t2_down = x2 - radius * sin(slope1);
        double y_t2_down = y2 + radius * cos(slope1);

        double x_t3_up = x2 + radius * sin(slope2);
        double y_t3_up = y2 - radius * cos(slope2);
        double x_t4_up = x3 + radius * sin(slope2);
        double y_t4_up = y3 - radius * cos(slope2);

        double x_t3_down = x2 - radius * sin(slope2);
        double y_t3_down = y2 + radius * cos(slope2);
        double x_t4_down = x3 - radius * sin(slope2);
        double y_t4_down = y3 + radius * cos(slope2);

        if (fabs(slope1 - slope2) > 1e-6) {
            // 不平行的情况
            Point intersection1 = line_intersection(
                (Point){x_t1_up, y_t1_up},
                (Point){x_t2_up, y_t2_up},
                (Point){x_t3_up, y_t3_up},
                (Point){x_t4_up, y_t4_up}
            );

            if (intersection1.x != 0.0 || intersection1.y != 0.0) {
                intersection_points[*num_intersections] = intersection1;
                (*num_intersections)++;
            }

            Point intersection2 = line_intersection(
                (Point){x_t1_down, y_t1_down},
                (Point){x_t2_down, y_t2_down},
                (Point){x_t3_down, y_t3_down},
                (Point){x_t4_down, y_t4_down}
            );

            if (intersection2.x != 0.0 || intersection2.y != 0.0) {
                intersection_points[*num_intersections] = intersection2;
                (*num_intersections)++;
            }
        } else {
            // 平行的情况，计算中间圆与切线的两个交点
            Point intersection1 = {x2 + radius * sin(slope1), y2 - radius * cos(slope1)};
            intersection_points[*num_intersections] = intersection1;
            (*num_intersections)++;

            Point intersection2 = {x2 - radius * sin(slope1), y2 + radius * cos(slope1)};
            intersection_points[*num_intersections] = intersection2;
            (*num_intersections)++;
        }
    }
}

int main() {
    Point centers[] = {
        {1.0, 1.0},
        {2.0, 2.0},
        {3.0, 3.0},
        {4.0, 4.0},
        {5.0, 4.0},
        {6.0, 4.0},
        {6.0, 3.0},
        {6.0, 2.0},
        {6.0, 1.0}
    };
    double radius = 1.0;

    Point intersection_points[100];
    int num_intersections = 0;

    calculate_all_tangent_lines(centers, radius, intersection_points, &num_intersections);

    // 打印计算结果
    printf("Intersection Points:\n");
    for (int i = 0; i < num_intersections; i++) {
        printf("(%.6lf, %.6lf)\n", intersection_points[i].x, intersection_points[i].y);
    }

    return 0;
}
